package org.shj.algorithm.dhsjjg.sort;

public class Sort {

	public static void main(String[] args){
		int[] sortArr = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20};
//		bubbleSort2(sortArr);
//		selectSort1(sortArr);
//		insertSort(sortArr);
//		shellSort(sortArr);
		heapSort(sortArr);
//		mergeSort(sortArr);
//		quickSort(sortArr);
		print(sortArr);
	}
	
	//此算法效率较低, 见 bubbleSort1.png
	public static void bubbleSort1(int[] sortArr){
		for(int i = 0 ; i < sortArr.length; i++){
			for(int j = i + 1; j < sortArr.length; j++){
				if(sortArr[i] > sortArr[j]){
					swap(sortArr, i, j);
				}
			}
		}
		print(sortArr);
	}
	
	//见bubbleSort2.png
	public static void bubbleSort2(int[] r){
		for(int i = 0 ; i < r.length; i++){
			for(int j = r.length - 1; j > i; j--){
				if(r[j] < r[j - 1]){
					swap(r, j, j-1);
				}
			}
		}
	}
	
	//避免某些有序情形下的重复比较
	public static void bubbleSort3(int[] r){
		boolean flag = true;
		for(int i = 0 ; i < r.length && flag; i++){
			flag = false;
			for(int j = r.length - 1 ; j > i; j--){
				if( r[j] < r[j-1]){
					swap(r, j, j-1);
					flag = true;
				}
			}
		}
	}
	
	//性能略优于冒泡排序
	public static void selectSort1(int[] r){
		int i, j, min;
		for(i = 0 ; i < r.length; i++){
			min = i;
			for(j = i + 1; j < r.length; j++){
				if(r[min] > r[j]){
					min = j;
				}
			}
			if( i != min){
				swap(r, i, min);
			}
		}
	}
	
	//插入排序比简单选择排序好一点
	public static void insertSort(int[] r){
		int i, j, tmp;
		for(i = 1 ; i < r.length; i++){
			if(r[i] < r[i-1]){
				tmp = r[i];
				for(j = i - 1; j >= 0 && r[j] > tmp; j--){
					r[j+1] = r[j]; //记录后移
				}
				r[j+1] = tmp;
			}
		}
	}

	/**
	 * 希尔排序, 见 pic/希尔排序
	 * @param r
	 */
	public static void shellSort(int[] r){
		int i, j, tmp;
		int increment = r.length;
		do{
			increment = increment / 3 + 1; //增量序列
			for(i = increment; i < r.length; i++){
				if(r[i] < r[i-increment]){ //需要将r[i]插入有序增量子表
					tmp = r[i];
					for(j = i - increment; j >= 0 && tmp < r[j]; j -= increment){
						r[j+increment] = r[j]; //记录后移
					}
					r[j+increment] = tmp;
				}
			}
		}while(increment > 1);
	}

	/**
	 * 堆排序
	 * 详细解释见： https://mp.weixin.qq.com/s/bpHVbUArp6OUB_ITSH1uew
	 * @param r
	 */
	public static void heapSort(int[] r){
		int i;
		for( i = r.length/2-1 ; i >= 0; i--){ //把数组构建成一个大顶堆
			heapAdjust(r, i, r.length - 1);
		}
		for(i = r.length - 1; i > 0; i--){
			swap(r, 0, i);
			heapAdjust(r, 0, i-1); //将 r[1...i-1] 重新调整为大顶堆
		}
	}
	
	private static void heapAdjust(int[] r, int s, int m){
		int temp, j;
		temp = r[s];
		
		//当前结点下标为s时，由完全二叉树的性质得知，其左孩子下标为2*s, 其右孩子下标为2*s+1。
		for(j = 2 * s; j < m; j*=2){ //沿关键字较大的孩子结点向下筛选, 
			if(j < m && r[j] < r[j+1]){ // j<m （说明不是最后一个节点） 且右孩子大于左孩子
				++j;       // j为关键字中较大的记录的下标
			}
			if(temp >= r[j]){//双亲结点大于左右孩子，则不需要交换
				break; 
			}
			r[s] = r[j]; //把双亲结点设置为左右孩子中较大那个结点值
			s = j; //改变双亲结点序号为左右孩子中较大结点的序号，以便进入下一个循环时，找到此较大结点下面的较大的孩子结点
		}
		r[s] = temp;    //插入
	}
	
	public static void mergeSort(int[] r){
		mSort(r, r, 0, r.length - 1, r.length);
	}
	
	//将sr[s...t]归并排序为tr1[s...t]
	private static void mSort(int sr[], int tr1[], int s, int t, int maxSize){
		int m;
		int[] tr2 = new int[maxSize];
		if(s == t){
			tr1[s] = sr[s];
		}else{
			m = (s+t) / 2;           //将sr[s...t]平分为sr[s...m]和sr[m+1...t]
			mSort(sr, tr2, s, m,maxSize);    //递归将sr[s...m]归并为有序的tr2[s...m]
			mSort(sr, tr2, m+1, t,maxSize);  //递归将sr[m+1...t]归并为有序的tr2[m+1...t]
			merge(tr2, tr1, s, m, t);//将tr2[s...m]和tr2[m+1]...t]归并到tr1[s...t]
		}
	}
	
	private static void merge(int sr[], int tr[], int i, int m, int n){
		int j,k, y;
		for(j = m + 1, k = i; i <= m && j <= n; k++){ //将sr中记录由小到大归并入tr
			if(sr[i] < sr[j]){
				tr[k] = sr[i++];
			}else{
				tr[k] = sr[j++];
			}
		}
		if(i <= m){
			for(y = 0; y <= m-i; y++){
				tr[k+y] = sr[i+y]; //将剩余的 SR[i...m]复制到tr[]中
			}
		}
		if(j <= n){
			for(y = 0 ; y <= n-j; y++){
				tr[k+y] = sr[j+y]; //将剩余的 SR[j...n]复制到tr[]中
			}
		}
	}


	
	//快速排序对大数组比较有优势
	public static void quickSort(int[] r){
		qSort(r, 0, r.length - 1);
	}
	
	private static void qSort(int[] r, int low, int high){
		int pivot;
		
		while(low < high){
			pivot = partition(r, low, high);
			qSort(r, low, pivot - 1);
			low = pivot + 1;
		}
	}


	private static int partition(int[] r, int low, int high){
		int pivotkey;
		
		int m = low + (high - low) / 2; //计算数组中间的元素下标
		if(r[low] > r[high]){
			swap(r,low,high);			//交换左端与右端数据，保证右端较大
		}
		
		if(r[m] > r[high]){				//交换中间与右端数据，保证中间较小
			swap(r,high,m);
		}
		
		if(r[m] > r[low]){				//交换中间与左端数据，保证中间较小
			swap(r,m,low);
		}
		
		pivotkey = r[low]; //经过上面的三次交换，low位置的值是一个中间值。
		int tmp = pivotkey;
		
		while(low < high){
			while(low < high && r[high] >= pivotkey){
				high--;
			}
			r[low] = r[high];
			while(low < high && r[low] <= pivotkey){
				low++;
			}
			r[high] = r[low];
		}
		r[low] = tmp;
		return low;
	}
	
	public static void print(int[] sortArr){
		for(int i = 0 ; i < sortArr.length; i++){
			System.out.print(sortArr[i]  + ", ");
		}
	}
	
	public static void swap(int[] r, int i, int j){
		int temp = r[i];
		r[i] = r[j];
		r[j] = temp;
	}
}
